There are no Cross References to Related Applications.
There is no Federally Sponsored R and D related to this application.
There is no Microfiche Appendix related to this application.
This invention relates to efficiently managing the dynamic allocation, access, and release of memory used in a computational environment. This memory may be used to store data or commands for a computational unit, such as a computer. This invention particularly applies to memory used in typical computational environments in which high utilization rates impair the performance of the computational unit, largely due to the need for memory management functions such as compaction and garbage collection, on behalf of the applications. More particularly, this invention relates to dynamic memory management, in which memory allocations and releases, as well as housekeeping functions in general, do not have substantially deterministic responses during execution of an application of the computational unit in the prior art.
Historically, memory used in a computational environment, such as a computer, has been expensive and of questionable reliability. The general belief was that this memory should be utilized or xe2x80x9cpackedxe2x80x9d as fully as possible. Methods for the efficient, here used in the sense of fully utilized, use of memory became standard, and have not been seriously questioned before this invention, though attempts have been made to reduce the impact on performance of such usage, and to make the operations more deterministic. Kevin D. Nilsen, U.S. Pat. No. 5,687,368, teaches the conventional view of the methods for efficient memory implementation. The ""368 patent addresses a major shortcoming of the prior art, which is loss of computational performance due to the need for memory management, also called housekeeping, to achieve efficient use of memory. The ""368 patent teaches the use of a hardware implementation to alleviate the problem of loss of performance in the computational unit. However, the ""368 patent does not teach reducing or eliminating housekeeping functions or mapping large, sparsely populated logical memory address space onto smaller, denser physical memory address space as in this invention. The ""368 patent also does not teach making housekeeping functions more deterministic in the way or to the extent that the present invention does. The traditional methods of the prior art, even when implemented in a hardware structure like that of the ""368 patent, copy data from memory location to memory location in order to compact and xe2x80x9cgarbage collectxe2x80x9d the data. Garbage collection is a term used to describe the processes in a computer which recover previously used memory space when it is no longer in use. Garbage collection also consists of re-organizing memory to reduce the unused spaces created within the stored information when unused memory space is recovered, a condition known as fragmentation. The prior art inherently reduces the performance of the computational unit, due to the need to perform these operations and the time consumed thereby. Further, these operations are inherently not substantially deterministic, since the iterative steps required have no easily determinable limit in the number of iterations. Basic assumptions in the prior art have been that memory should be optimized with respect to the utilization of the memory address space, rather than of the actual memory itself. Reliability was also considered to be a factor in utilizing available memory space as efficiently as possible. As a consequence, the atomic memory management data size was set in small blocks; usually 1024 bytes. Memory management systems (MMS) of the prior art then searched for memory not in use, often down to the individual block, in order that memory space could be freed as expeditiously and to as small a unit size as possible. This process is one of the housekeeping functions, and is commonly referred to as xe2x80x9cgarbage collectionxe2x80x9d. This process often requires the use of substantially indefinite numbers of iterations, making the loss in performance substantially not deterministic. The small size of the atomic memory unit often causes small pieces of memory, which are being used, to be interspersed with unused, or xe2x80x9cgarbagexe2x80x9d locations, a process known as xe2x80x9cfragmentationxe2x80x9d of memory. Since this could result in significant problems in accessing streams of data due to the necessity to access small locations which are not contiguous, a technique known as xe2x80x9ccompactionxe2x80x9d or xe2x80x9cdefragmentationxe2x80x9d has been employed. This causes special commands and routines to be required and frequently used. In the UNIX operating system environment, when programming in ANSI C, for example, function calls that directly or indirectly invoke these representative routines by allocating and releasing dynamic memory are known as xe2x80x9cmalloc( )xe2x80x9d, xe2x80x9ccalloc( )xe2x80x9d, xe2x80x9crealloc( )xe2x80x9d, and xe2x80x9cfree( )xe2x80x9d. Again, these functions and the directly or indirectly invoked representative routines require a substantially indefinite number of iterations, and are substantially not deterministic. Additionally, to aid the functions above and to better utilize available memory, various concepts such as xe2x80x9crelocatable memoryxe2x80x9d were developed and implemented, thereby allowing for more efficient routines for memory management functions such as compaction and defragmentation. Memory management functions, using relocatable memory, work by copying memory atomic units (objects) from one location in memory to another, to allow garbage fragments between valid objects to be combined into larger free memory areas. However, while improving the flexibility of the allocation process, relocatable memory also requires indefinite numbers of iterations, and further makes the time required for housekeeping functions substantially not deterministic.
The present invention recognizes the fact that computational systems are becoming larger, and garbage collection is becoming less deterministic, more complex, and requires a substantial amount of computational time to be expended that would otherwise be available for productive work by the computational unit.
It is an object of this invention to map a large, normally contiguous, section of the logical memory address space used to store dynamically created objects accessed by a computational unit such as a computer to a smaller physical memory address space. The need for housekeeping functions is reduced and may be preferably eliminated. Examples of housekeeping functions hereby reduced or eliminated are garbage collection and memory compaction. It is a further object of this invention to translate or map the addresses of a computational unit such as a computer, which may have a very large and sparsely populated logical memory address space, to the much smaller and denser physical memory address space of a physical memory. The physical memory address space of this invention is preferably of fixed size and statically located. Because housekeeping functions, which reduce system performance, are reduced and can be eliminated, the computational unit performance is thereby improved, and the execution of dynamic memory management processes becomes deterministic.
In accordance with a first embodiment of the present invention, a computational memory consisting of fixed sized modules of physical memory is formed. This is also referred to as xe2x80x9cprivate memory address spacexe2x80x9d herein. The associated physical memory is interfaced to a CPU and the xe2x80x9clogical memory address spacexe2x80x9d the CPU controls by means of a memory address mapping interface, referred to herein as a Dynamic Memory Manager (DMM).
The logical memory address space in today""s microprocessor based systems is defined by the size of the address bus. Large microprocessor systems tend to be 32 bits or 64 bits wide. Note that 32 bits can define a space of nearly 4.3 billion bytes (2**32) and 64 bits can define a space of nearly 185,000 trillion bytes (2**64). In contrast, the physical memory connected to the same system substantially ranges in size from 1 million bytes (2**20) to 1 billion bytes (2**30). This invention capitalizes on this vast difference in size between the logical memory address space supported by the address bus and the real world physical memory size utilized in most microprocessor systems.
As an example, a current workstation as a microprocessor system may have an address bus of 32 bits. Mapped to this logical memory address space by the CPU are several possible physical memories such as RAM, ROM, and flash plus physical devices such as disk drive controllers, video interfaces, and network interfaces. Each of these memories and devices require unique address space within the logical memory address space, the largest of which is most likely the RAM memory at, say, 128 megabytes (2**27). All the devices in the microprocessor system can be mapped into much less than half of the 32 bit address bus (2**31) leaving a high addressed 2.1 billion bytes (2**32 less the 2**31 noted above) for use by the DMM. In an example of utilizing this large, contiguous logical memory address space, the DMM partitions it into 32,768 individual elements, each of which is assumed to be 65,536 bytes. The starting address of each element in this example is substantially on a 65,536 byte (2**16) boundary. If each of the 32,768 elements were allocated at the same size, and the DMM controlled a (2**27) physical memory, each element would be 4,096 bytes. This is not to imply all elements must be the same size, this is not a requirement, nor is it likely to be found in a system. The purpose is to point out the DMM is constrained to allocate only as much physical memory as it controls.
To continue with the example, the CPU could access memory controlled by the DMM by placing a bus address on the system bus within substantially the range of (2**32 minus 2**31 and indicating if the memory access is a read or write operation. Note that most of the potential addresses are invalid and the preferred embodiment of the DMM will cause an invalid memory access trap to be generated when presented with an invalid address. A valid address would be one that the DMM had previously returned to the CPU during an allocation that has not since been released. Accesses past the starting address are valid, as long as the addresses are not greater than the starting address of the allocation plus substantially the length of the dynamic memory object.
In general terms, logical addresses on the memory bus are mapped by the DMM into the physical memory, which is defined by a physical memory address space smaller than the logical memory address space. By this invention, the physical memory address space is made accessible over substantially the range of the large, sparsely populated logical memory address space.
This allows the containment of bad data or fragmented areas without the need for compaction or garbage collection, etc., which are included in the functions commonly known in the art as xe2x80x9chousekeepingxe2x80x9d functions. For example, the present invention makes the common UNIX and ANSI xe2x80x9cCxe2x80x9d functions malloc( ), calloc( ), realloc( ), and free( ) faster and more deterministic in their execution time. The CPU xe2x80x9coverheadxe2x80x9d or performance-degrading operations required by these functions, or other so called xe2x80x9cbackground routinesxe2x80x9d to perform delayed xe2x80x9chousekeepingxe2x80x9d, is reduced, and preferably eliminated.
In accordance with a second embodiment of the present invention a hardware implementation is incorporated within a CPU, such as inside an integrated circuit chip which includes the CPU and computational memory functions. In addition to the above mentioned invention improvements, performance is increased due to the CPU having on chip access to the DMM and not being required to contend with other system bus transfers to access dynamic memory.
In accordance with a third embodiment of the present invention, software (also called xe2x80x9ccodexe2x80x9d) is loaded into the CPU. The code, commonly part of the host processor operating system, implements the function of this invention by mapping a large, contiguous section of the logical address space on the memory bus to the physical memory address space for specific physical memory addresses. This allows sparsely utilized logically redundant memory address space to be mapped to fixed size and statically located physical address space. The mapping thereby creates a physical address space that appears to be as large as the logical memory address space. This is particularly useful in virtual machine systems such as the JAVA Application Environment (JAE) where object addresses reference virtual memory that must be allocated to physical locations. In this invention the allocation from logical or virtual memory to physical memory locations is greatly simplified compared to the prior art.